Computer Vision - Seam Carving

Jacky Baltes
National Taiwan Normal University
Taipei, Taiwan
jacky.baltes@ntnu.edu.tw

19 April 2021

Seam Carving

Intelligent resize for images
https://i.postimg.cc/5NkcFtVS/sample-image.jpg https://i.postimg.cc/5NkcFtVS/sample-image.jpg

Seam Carving

System Message: ERROR/3 (<string>, line 5)

Content block expected for the "container" directive; none found.

.. container:: jb-text


https://i.postimg.cc/5NkcFtVS/sample-image.jpg

System Message: ERROR/3 (<string>, line 11)

Error in "image" directive: no content permitted.

.. image:: https://i.postimg.cc/5NkcFtVS/sample-image.jpg
 :width: 10%

  Detail is lost when resizing the image

  Intelligent resize for images, focus on "interesting" parts

Seam Carving

https://i.postimg.cc/5NkcFtVS/sample-image.jpg https://i.postimg.cc/5NkcFtVS/sample-image.jpg

Detail is lost when resizing the image

Intelligent resize for images, focus on "interesting" parts

Seam Carving

https://i.postimg.cc/5NkcFtVS/sample-image.jpg https://i.postimg.cc/5NkcFtVS/sample-image.jpg

Detail is lost when resizing the image

Intelligent resize for images, focus on "interesting" parts

Energy

Interesting? Measure of information associated with a pixel

Measure how different from the background/its neighbors

One way to formalize energy is the magnitude of the gradient

% matplotlib notebook 

import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
import math
import random

origImage = Image.open( img1.getLocalName() )
width, height = origImage.size

nw, nh = width//4, height
origImage = origImage.resize((nw,nh))
oimg = np.array( origImage )
#oimg = oimg[200:300,430:530]

ax.imshow( oimg, cmap='gray')

balir=addJBFigure("balir", 0, 0, fig )
% matplotlib notebook 

import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
import math
import random

origImage = Image.open( img1.getLocalName() )
width, height = origImage.size

nw, nh = width//4, height
origImage = origImage.resize((nw,nh))
oimg = np.array( origImage )
#oimg = oimg[200:300,430:530]

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg, cmap='gray')

balir=addJBFigure("balir", 0, 0, fig )
% matplotlib notebook 

import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
import math
import random

origImage = Image.open( img1.getLocalName() )
width, height = origImage.size

nw, nh = width//4, height//4
origImage = origImage.resize((nw,nh))
oimg = np.array( origImage )
#oimg = oimg[200:300,430:530]

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg, cmap='gray')

balir=addJBFigure("balir", 0, 0, fig )
% matplotlib notebook 

import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
import math
import random

origImage = Image.open( img1.getLocalName() )
width, height = origImage.size

nw, nh = width//2, height//2
origImage = origImage.resize((nw,nh))
oimg = np.array( origImage )
#oimg = oimg[200:300,430:530]

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg, cmap='gray')

balir=addJBFigure("balir", 0, 0, fig )
%matplotlib notebook 

def calcGradient( img ):
  height, width, depth = img.shape
  grad = np.zeros( ( height, width )  )
  #print(height, width, depth )
  for y in range( height ):
    for x in range( width ):
      gx, cnt = 0.0, 0
      for dx, dy in [ [-1,-1], [0,-1], [1,-1], [-1,0], [1,0], [1,-1], [1,0], [1,1] ]:
        x1 = x + dx
        y1 = y + dy
        if ( x1 >= 0 ) and ( x1 < width ) and ( y1 >= 0 ) and ( y1 < height ):
          d = np.sum( np.abs( img[y,x] - img[y1,x1] ) )
          
          gx = gx + d
          cnt = cnt + 1
      grad[y,x] = gx/cnt
  return grad
%matplotlib notebook 

def normalizeImage( img ):
  return ( grad - np.min(grad) ) * 255.0 / np.max(grad)

#img = np.random.random( (10,10,3) ) *255
#img[0:10,5:8,:] = 128

grad = calcGradient( oimg )
gradNorm = normalizeImage( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( gradNorm, cmap = 'gray' )

bali10 = addJBFigure( "bali10", 0, 0, fig )
% matplotlib notebook 

import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
import math
import random

origImage = Image.open( img1.getLocalName() )
width, height = origImage.size

nw, nh = width//2, height//2
origImage = origImage.resize((nw,nh))
oimg = np.array( origImage )
#oimg = oimg[200:300,430:530]

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg, cmap='gray')

balir=addJBFigure("balir", 0, 0, fig )
%matplotlib notebook 

def calcGradient( img ):
  height, width, depth = img.shape
  grad = np.zeros( ( height, width )  )
  #print(height, width, depth )
  for y in range( height ):
    for x in range( width ):
      gx, cnt = 0.0, 0
      for dx, dy in [ [-1,-1], [0,-1], [1,-1], [-1,0], [1,0], [1,-1], [1,0], [1,1] ]:
        x1 = x + dx
        y1 = y + dy
        if ( x1 >= 0 ) and ( x1 < width ) and ( y1 >= 0 ) and ( y1 < height ):
          d = np.sum( np.abs( img[y,x] - img[y1,x1] ) )
          
          gx = gx + d
          cnt = cnt + 1
      grad[y,x] = gx/cnt
  return grad
%matplotlib notebook 

def normalizeImage( img ):
  return ( grad - np.min(grad) ) * 255.0 / np.max(grad)

#img = np.random.random( (10,10,3) ) *255
#img[0:10,5:8,:] = 128

grad = calcGradient( oimg )
gradNorm = normalizeImage( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( gradNorm, cmap = 'gray' )

bali10 = addJBFigure( "bali10", 0, 0, fig )

Remove one continuous seam for colums and rows

Find the minimum energy seam to remove for rows and columns

Time complexity of the algorithm (runtime) Order of $$ O( 3^{h} ) $$

Dynamic programming

  • Set of reused sub problems (caching)
  • Combine the sub-problems into overall solution

Remove one continuous seam for colums and rows

Find the minimum energy seam to remove for rows and columns

Time complexity of the algorithm (runtime) Order of $$ O( 3^{h} ) $$

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

xs = np.arange(height)
ys = np.array( [ 3 ** x for x in xs ] )

ax.plot(xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()
fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.title("Computational Complexity")

xs = np.arange(height)
ys = np.array( [ 3 ** x for x in xs ] )

ax.plot(xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()
fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_title("Computational Complexity")

xs = np.arange(height)
ys = np.array( [ 3 ** x for x in xs ] )

ax.plot(xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()
fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_title("Computational Complexity")

xs = np.arange(height)
print(xs)
ys = np.array( [ 3 ** x for x in xs ] )
print(ys)

ax.plot(xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()
[  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17
  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35
  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53
  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71
  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89
  90  91  92  93  94  95  96  97  98  99 100 101 102 103 104 105 106 107
 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161
 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197
 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215
 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233
 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251
 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269
 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287
 288 289 290 291 292 293 294]
[                   1                    3                    9
                   27                   81                  243
                  729                 2187                 6561
                19683                59049               177147
               531441              1594323              4782969
             14348907             43046721            129140163
            387420489           1162261467           3486784401
          10460353203          31381059609          94143178827
         282429536481         847288609443        2541865828329
        7625597484987       22876792454961       68630377364883
      205891132094649      617673396283947     1853020188851841
     5559060566555523    16677181699666569    50031545098999707
   150094635296999121   450283905890997363  1350851717672992089
  4052555153018976267 -6289078614652622815  -420491770248316829
 -1261475310744950487 -3784425932234851461  7093466277004997233
  2833654757305440083  8500964271916320249  7056148742039409131
  2721702152408675777  8165106457226027331  6048575297968530377
  -301018179803960485  -903054539411881455 -2709163618235644365
 -8127490854706933095 -5935728490411247669   639558602475808609
  1918675807427425827  5756027422282277481 -1178661806862719173
 -3535985420588157519  7838787811945079059  5069619362125685561
 -3237885987332494933  8733086111712066817  7752514261426648835
  4810798710570394889 -4014347941998366949  6403700247714450769
   764356669433800691  2293070008301402073  6879210024904206219
  2190886001003067041  6572658003009201123  1271229935318051753
  3813689805954155259 -7005674655847085839 -2570279893831705901
 -7710839681495117703 -4685774970775801493  4389419161382147137
 -5278486589563110205  2611284305020221001  7833852915060663003
  5054814671472437393 -3282300059292239437  8599843895832833305
  7352787613788948299  3611618767657293281 -7611887770737671773
 -4388919238503463703  5279986358199160507 -2606784999112070095
 -7820354997336210285 -5014320918299079239  3403781318812313899
 -8235400117272609919 -6259456278108278141  -331624760615282807
  -994874281845848421 -2984622845537545263 -8953868536612635789
 -8414861536128355751 -6797840534675515637 -1946777530316995295
 -5840332590950985885   925746300856593961  2777238902569781883
  8331716707709345649  6548406049418485331  1198474074545904377
  3595422223637713131 -7660477402796412223 -4534688134679685053
  4842679669670496457 -3918705064698062245  6690628879615364881
  1625142565136543027  4875427695409629081 -3820460987480664373
  6985361111267558497  2509339260093123875  7528017780279371625
  4137309267128563259 -6034816272323861839   342295256737966099
  1026885770213898297  3080657310641694891 -9204772141784466943
 -9167572351643849213 -9055972981221996023 -8721174869956436453
 -7716780536159757743 -4703597534769721613  4335951469400386777
 -5438889665508391285  2130075077184377761  6390225231553133283
   723931620949848233  2171794862849544699  6515384588548634097
  1099409691936350675  3298229075809052025 -8552056846282395541
 -7209426465137635007 -3181535321703353405  8902138108599491401
  8259670252088922587  6332266682557216145   550055973962096819
  1650167921886290457  4950503765658871371 -3595232776732937503
  7661045743510739107  4536393156822665705 -4837564603241554501
  3934050263984888113 -6644593281754887277 -1487035771555110215
 -4461107314665330645  5063422129713559681 -3256477684568872573
  8677311020002933897  7585188986299250075  4308822885188198609
 -5520275418144955789  1885917819274684249  5657753457824052747
 -1473483700237393375 -4420451100712180125  5185390771573011241
 -2890571758990517893 -8671715276971553679 -7568401757205109421
 -4258461197905776647  5671360479992221675 -1432662633732886591
 -4297987901198659773  5552780370113572297 -1788402963368834725
 -5365208890106504175  2351117403390039091  7053352210170117273
  2713312556800800203  8139937670402400609  5973068937497650211
  -527537261216600983 -1582611783649802949 -4747835350949408847
  4203238020861325075 -5837030011125576391   935654040332822443
  2806962120998467329  8420886362995401987  6815915015276654345
  2001000972120411419  6003002916361234257  -437735324625848845
 -1313205973877546535 -3939617921632639605  6627890308811632801
  1436926852725346787  4310780558176040361 -5514402399181430533
  1903536876165260017  5710610628495780051 -1314912188222211463
 -3944736564666634389  6612534379709648449  1390859065419393731
  4172577196258181193 -5929012484935008037   659706618904527505
  1979119856713582515  5937359570140747545  -634665363287308981
 -1903996089861926943 -5711988269585780829  1310779264952209129
  3932337794856627387 -6649730689139669455 -1502447993709456749
 -4507343981128370247  4924712130324440875 -3672607682736228991
  7428921025500864643  3840019002793042313 -6926687065330424677
 -2333317122281722415 -6999951366845167245 -2553110026825950119
 -7659330080477850357 -4531246167723999455  4853005570537553251
 -3887727362096891863  6783561987418876027  1903941888547076465
  5711825665641229395 -1311267076785863431 -3933801230357590293
  6645340382636780737  1489277074200790595  4467831222602371785
 -5043250405902436261  3316992856002242833 -8495765505702823117
 -7040552443398917735 -2674913256487201589 -8024739769461604767
 -5627475234675262685  1564318369683763561  4692955109051290683
 -4367878746555679567  5343107834042512915 -2417420571582012871
 -7252261714746038613 -3310041070528564223  8516620862123858947
  7103118512662025225  2862611464276524059  8587834392829572177
  7316759104779164915  3503533240627943129 -7936144351825722229
 -5361688981767615071  2361677128406706403  7085031385220119209
  2808350081950806011  8425050245852418033  6828406663847702483
  2038475917833555833  6115427753500667499  -100460813207549119
  -301382439622647357  -904147318867942071 -2712441956603826213
 -8137325869811478639 -5965233535724884301   551043466534898713
  1653130399604696139  4959391198814088417 -3568570477267286365
  7741032641907692521  4776353852013525947 -4117682517668973775
  6093696520702630291  -165654511601660743  -496963534804982229
 -1490890604414946687 -4472671813244840061  5028728633975031433
 -3360558171784457317  8365069558356179665  6648464601358987379
  1498649730367410521]
fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_title("Computational Complexity")

xs = np.arange(height)
#print(xs)
ys = np.array( [ 3 ** x for x in xs ] )
#print(ys)

ax.plot(xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()
fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_title("Computational Complexity")

xs = np.arange(height)
#print(xs)
ys = np.array( [ 3 ** x for x in xs ] )
#print(ys)

ax.plot( ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()
fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_title("Computational Complexity")

xs = np.arange(20)
#print(xs)
ys = np.array( [ 3 ** x for x in xs ] )
#print(ys)

ax.plot( xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()
fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_title("Computational Complexity")

xs = np.arange(height)
#print(xs)
ys = [ 3 ** x for x in xs ]
#print(ys)

ax.plot( xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()
fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_title("Computational Complexity")

xs = np.arange(20)
#print(xs)
ys = [ 3 ** x for x in xs ]
#print(ys)

ax.plot( xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()

Dynamic programming

  • Set of reused sub problems (caching)
  • Combine the sub-problems into overall solution
Sum
2
Sum...
Sum
5
Sum...
Sum
3
Sum...
Viewer does not support full SVG 1.1
Sum
2
Sum...
Sum
5
Sum...
Sum
3
Sum...
Viewer does not support full SVG 1.1

Dynamic Programming in Seam Carving

Minimum energy seam will go through the top neighbor with the minimum energy

Minimum energy path through that pixel will be gradient of pixel + minimum of path to top neighbors

Dynamic Programming in Seam Carving

Minimum energy seam will go through the top neighbor with the minimum energy

Minimum energy path through that pixel will be gradient of pixel + minimum of path to top neighbors

Dynamic Programming in Seam Carving

Minimum energy seam will go through the top neighbor with the minimum energy

Minimum energy path through that pixel will be gradient of pixel + minimum of path to top neighbors

timg = np.random.randint(0,99,(5,10))

t1imgT = createTable( timg )
timg = np.random.randint(0,99,(5,10))

t1imgT = createTable( timg )

display(HTML(t1imgT))
13 67 44 64 35 73 29 10 23 97
20 12 78 65 21 38 95 61 5 11
52 3 88 12 98 30 19 69 16 91
84 36 40 65 11 28 28 71 16 31
47 78 47 71 45 93 13 9 72 89
timg = np.random.randint(0,99,(5,10))

t1imgT = createTable( timg )

display(HTML(f"""
<div style="background:grey">
{t1imgT}
</div>
""""))
timg = np.random.randint(0,99,(5,10))

t1imgT = createTable( timg )

display(HTML(f'<div style="background:grey">{t1imgT}</div>'))
2 60 60 89 25 42 71 31 74 9
0 89 6 87 44 73 15 65 2 8
11 42 8 46 11 6 50 6 29 40
30 87 51 85 22 15 20 63 65 39
53 65 90 30 96 86 36 39 55 86
Path [8, 8, 8, 8, 8] = 40
Path [9, 8, 8, 8, 7] = 40
Path [4, 3, 3, 3, 3] = 16
Path [10, 9, 8, 7, 6] = 40
Path [9, 8, 7, 6, 5] = 35
Path [9, 8, 8, 8, 8] = 160
Path [7, 7, 6, 5, 5] = 247
Path [1, 1, 1, 0, 0] = 274
Path [9, 8, 7, 6, 5] = 123
Path [9, 9, 9, 9, 8] = 151

Greedy Algorithm

An initially attractive solution may be to choose the lower neighbor with the minimum energy.

Greedily choosing what looks to be the best solution at each step in our search

This may lead the search down the wrong path with no way to recover

In this domain, the local minimum is not good enough

Dynamic Programming in Seam Carving

Minimum energy seam will go through the top neighbor with the minimum energy

Minimum energy path through that pixel will be gradient of pixel + minimum of path to top neighbors

%matplotlib notebook 

def findMinEnergySeam( grad ):
  height, width = grad.shape
  #print(grad.shape)
  carve = np.zeros((height, width))

  max = None
  carve[0,:] = grad[0,:]
  for y in range(1,height):
    for x in range(width):
      emin = None
      for tx, ty in [ [x-1, y-1], [x, y-1], [x+1, y-1] ]:
        if (tx >= 0) and ( tx < width ) and (ty >= 0 ) and (ty < height ):
          #print('tx',tx,'ty', ty, 'emin', emin, 'g[y,x]', grad[y,x], 'g[ty,tx]', grad[ty,tx] )
          if ( emin is None ) or ( grad[y,x] + grad[ty, tx] < emin ):
            emin = grad[y,x] + grad[ty, tx]
            #print('Setting emin', emin)
      carve[y,x] = emin
      if max is None or emin > max:
        max = emin
  return carve

carve = findMinEnergySeam( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( carve, cmap = 'gray' )
sol1 = addJBFigure("sol1", 0, 0, fig )
%matplotlib notebook 

def findMinEnergySeam( grad ):
  height, width = grad.shape
  #print(grad.shape)
  carve = np.zeros((height, width))

  max = None
  carve[0,:] = grad[0,:]
  for y in range(1,height):
    for x in range(width):
      emin = None
      for tx, ty in [ [x-1, y-1], [x, y-1], [x+1, y-1] ]:
        if (tx >= 0) and ( tx < width ) and (ty >= 0 ) and (ty < height ):
          #print('tx',tx,'ty', ty, 'emin', emin, 'g[y,x]', grad[y,x], 'g[ty,tx]', grad[ty,tx] )
          if ( emin is None ) or ( grad[y,x] + grad[ty, tx] < emin ):
            emin = grad[y,x] + grad[ty, tx]
            #print('Setting emin', emin)
      carve[y,x] = emin
      if max is None or emin > max:
        max = emin
  return carve

carve = findMinEnergySeam( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( carve, cmap = 'gray' )
sol1 = addJBFigure("sol1", 0, 0, fig )
% matplotlib notebook 
def findPath( carve ):
  height, width = carve.shape
  minIndex = None
  min = None
  for x in range(width):
    if min is None or carve[height-1, x] < min:
      minIndex = x
      min = carve[height-1, x]
  
  cx = minIndex
  path = [ [ height-1, cx]]
  
  for y in range( height-2, -1, -1 ):
    min = None
    minX = None
    for dx in [ cx-1, cx, cx+1 ]:
      if ( dx >= 0 ) and ( dx < width ):
        if min is None or carve[y,dx] < min:
          min = carve[y,dx]
          minX = dx
    cx = minX
    path.append([ y, cx ] )
  return path

minPath = np.array( findPath(carve) )
#print(minPath )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg )
ax.plot( minPath[:,1], minPath[:,0], 'b-', linewidth=3 )         
sol2 = addJBFigure( "sol2", 0, 0, fig )       
def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  c = min_index
  path = [c]
  print( f'Found minimum start', min_index, min)

p = greedy_seam(t1img)
def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  c = min_index
  path = [c]
  print( f'Found minimum start', min_index, min)

p = greedy_seam(timg)
Found minimum start 0 2
def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [x]
  for y in range(1,height):
    min = None
    min_index = None

    for dx in [-1, 0, 1]:
      xd = x +dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
      path.append(xd)
  return path
  
p = greedy_seam(timg)
def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [x]
  for y in range(1,height):
    min = None
    min_index = None

    for dx in [-1, 0, 1]:
      xd = x +dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
      path.append(xd)
  return path

p = greedy_seam(timg)
print('path', p)
path [0, -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1]
def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [x]
  for y in range(1,height):
    min = None
    min_index = None
    x2 = None
    for dx in [-1, 0, 1]:
      xd = x + dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
          x2 = xd
    x = x2
    path.append(x)
  return path

p = greedy_seam(timg)
print('path', p)
path [0, 0, 0, 0, 0]
def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [x]
  for y in range(1,height):
    min = None
    min_index = None
    x2 = None
    for dx in [-1, 0, 1]:
      xd = x + dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
          x2 = xd
    x = x2
    path.append(x)
  return path

p = greedy_seam(timg[:,1:10])
print('path', p)
path [8, 7, 6, 5, 5]
def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [x]
  for y in range(1,height):
    min = None
    min_index = None
    x2 = None
    for dx in [-1, 0, 1]:
      xd = x + dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
          x2 = xd
    x = x2
    path.append(x)
  return path

p = greedy_seam(timg[:,1:10])
print('path', p, 'energy', calc_energy(timg[:,1:10]))
def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [x]
  for y in range(1,height):
    min = None
    min_index = None
    x2 = None
    for dx in [-1, 0, 1]:
      xd = x + dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
          x2 = xd
    x = x2
    path.append(x)
  return path

p = greedy_seam(timg[:,1:10])
print('path', p, 'energy', calc_energy(timg[:,1:10], p))
path [8, 7, 6, 5, 5] energy 290
p = findMinEnergySeam( timg[:,1:10] )
print(p)
[[ 60.  60.  89.  25.  42.  71.  31.  74.   9.]
 [149.  66. 112.  69.  98.  46.  96.  11.  17.]
 [ 48.  14.  52.  55.  21.  65.   8.  31.  42.]
 [ 95.  59.  93.  28.  21.  26.  69.  71.  68.]
 [116. 141.  52. 111. 101.  51.  59.  94. 125.]]
carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(createTable(carve) ) )

p = findPath( carve )

print(p)
[[4, 5], [3, 4], [2, 4], [1, 5], [0, 6]]
60.0 60.0 89.0 25.0 42.0 71.0 31.0 74.0 9.0
149.0 66.0 112.0 69.0 98.0 46.0 96.0 11.0 17.0
48.0 14.0 52.0 55.0 21.0 65.0 8.0 31.0 42.0
95.0 59.0 93.0 28.0 21.0 26.0 69.0 71.0 68.0
116.0 141.0 52.0 111.0 101.0 51.0 59.0 94.0 125.0
carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

print(p)
[[4, 5], [3, 4], [2, 4], [1, 5], [0, 6]]
60.0 60.0 89.0 25.0 42.0 71.0 31.0 74.0 9.0
149.0 66.0 112.0 69.0 98.0 46.0 96.0 11.0 17.0
48.0 14.0 52.0 55.0 21.0 65.0 8.0 31.0 42.0
95.0 59.0 93.0 28.0 21.0 26.0 69.0 71.0 68.0
116.0 141.0 52.0 111.0 101.0 51.0 59.0 94.0 125.0
carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

print('Path', p, 'Energy', calc_energy(p) )
60.0 60.0 89.0 25.0 42.0 71.0 31.0 74.0 9.0
149.0 66.0 112.0 69.0 98.0 46.0 96.0 11.0 17.0
48.0 14.0 52.0 55.0 21.0 65.0 8.0 31.0 42.0
95.0 59.0 93.0 28.0 21.0 26.0 69.0 71.0 68.0
116.0 141.0 52.0 111.0 101.0 51.0 59.0 94.0 125.0
carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

print('Path', p, 'Energy', calc_energy(timg[:,1:10], p) )
Path [[4, 5], [3, 4], [2, 4], [1, 5], [0, 6]] Energy [260 148]
60.0 60.0 89.0 25.0 42.0 71.0 31.0 74.0 9.0
149.0 66.0 112.0 69.0 98.0 46.0 96.0 11.0 17.0
48.0 14.0 52.0 55.0 21.0 65.0 8.0 31.0 42.0
95.0 59.0 93.0 28.0 21.0 26.0 69.0 71.0 68.0
116.0 141.0 52.0 111.0 101.0 51.0 59.0 94.0 125.0
carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

p2 = [ p2 for p1,p2 in p.reverse() ]
print(p2)
print('Path', p, 'Energy', calc_energy(timg[:,1:10], p2 ) )
60.0 60.0 89.0 25.0 42.0 71.0 31.0 74.0 9.0
149.0 66.0 112.0 69.0 98.0 46.0 96.0 11.0 17.0
48.0 14.0 52.0 55.0 21.0 65.0 8.0 31.0 42.0
95.0 59.0 93.0 28.0 21.0 26.0 69.0 71.0 68.0
116.0 141.0 52.0 111.0 101.0 51.0 59.0 94.0 125.0
carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

p2 = [ p2 for p1,p2 in reverse(p) ]
print(p2)
print('Path', p, 'Energy', calc_energy(timg[:,1:10], p2 ) )
60.0 60.0 89.0 25.0 42.0 71.0 31.0 74.0 9.0
149.0 66.0 112.0 69.0 98.0 46.0 96.0 11.0 17.0
48.0 14.0 52.0 55.0 21.0 65.0 8.0 31.0 42.0
95.0 59.0 93.0 28.0 21.0 26.0 69.0 71.0 68.0
116.0 141.0 52.0 111.0 101.0 51.0 59.0 94.0 125.0
carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

p2 = [ p2 for p1,p2 in reversed(p) ]
print(p2)
print('Path', p, 'Energy', calc_energy(timg[:,1:10], p2 ) )
[6, 5, 4, 4, 5]
Path [[4, 5], [3, 4], [2, 4], [1, 5], [0, 6]] Energy 263
60.0 60.0 89.0 25.0 42.0 71.0 31.0 74.0 9.0
149.0 66.0 112.0 69.0 98.0 46.0 96.0 11.0 17.0
48.0 14.0 52.0 55.0 21.0 65.0 8.0 31.0 42.0
95.0 59.0 93.0 28.0 21.0 26.0 69.0 71.0 68.0
116.0 141.0 52.0 111.0 101.0 51.0 59.0 94.0 125.0
carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

p2 = [ p2 for p1,p2 in reversed(p) ]

print('Path', p, 'Energy', calc_energy(timg[:,1:10], p2 ) )
Path [[4, 5], [3, 4], [2, 4], [1, 5], [0, 6]] Energy 263
60.0 60.0 89.0 25.0 42.0 71.0 31.0 74.0 9.0
149.0 66.0 112.0 69.0 98.0 46.0 96.0 11.0 17.0
48.0 14.0 52.0 55.0 21.0 65.0 8.0 31.0 42.0
95.0 59.0 93.0 28.0 21.0 26.0 69.0 71.0 68.0
116.0 141.0 52.0 111.0 101.0 51.0 59.0 94.0 125.0

Seam Carving

Path [(0, 5), (1, 5), (2, 4), (3, 3), (4, 2)] = 301
Path [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0)] = 96
Path [(0, 2), (1, 1), (2, 0), (3, 0), (4, 0)] = 243
Path [(0, 4), (1, 3), (2, 2), (3, 2), (4, 1)] = 236
Path [(0, 4), (1, 4), (2, 3), (3, 2), (4, 1)] = 231

Greedy Algorithm

An initially attractive solution may be to choose the lower neighbor with the minimum energy.

Greedily choosing what looks to be the best solution at each step in our search

This may lead the search down the wrong path with no way to recover

In this domain, the local minimum is not good enough

def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [x]
  for y in range(1,height):
    min = None
    min_index = None
    x2 = None
    for dx in [-1, 0, 1]:
      xd = x + dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
          x2 = xd
    x = x2
    path.append((y,x))
  return path

p = greedy_seam(timg[:,1:10])
print('path', p, 'energy', calc_energy(timg[:,1:10], p))
def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [(0,x)]
  for y in range(1,height):
    min = None
    min_index = None
    x2 = None
    for dx in [-1, 0, 1]:
      xd = x + dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
          x2 = xd
    x = x2
    path.append((y,x))
  return path

p = greedy_seam(timg[:,1:10])
print('path', p, 'energy', calc_energy(timg[:,1:10], p))
path [(0, 8), (1, 7), (2, 6), (3, 5), (4, 5)] energy 73

Dynamic Programming in Seam Carving

Minimum energy seam will go through the top neighbor with the minimum energy

Minimum energy path through that pixel will be gradient of pixel + minimum of path to top neighbors

%matplotlib notebook 

def findMinEnergySeam( grad ):
  height, width = grad.shape
  #print(grad.shape)
  carve = np.zeros((height, width))

  max = None
  carve[0,:] = grad[0,:]
  for y in range(1,height):
    for x in range(width):
      emin = None
      for tx, ty in [ [x-1, y-1], [x, y-1], [x+1, y-1] ]:
        if (tx >= 0) and ( tx < width ) and (ty >= 0 ) and (ty < height ):
          #print('tx',tx,'ty', ty, 'emin', emin, 'g[y,x]', grad[y,x], 'g[ty,tx]', grad[ty,tx] )
          if ( emin is None ) or ( grad[y,x] + grad[ty, tx] < emin ):
            emin = grad[y,x] + grad[ty, tx]
            #print('Setting emin', emin)
      carve[y,x] = emin
      if max is None or emin > max:
        max = emin
  return carve

carve = findMinEnergySeam( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( carve, cmap = 'gray' )
sol1 = addJBFigure("sol1", 0, 0, fig )
% matplotlib notebook 
def findPath( carve ):
  height, width = carve.shape
  minIndex = None
  min = None
  for x in range(width):
    if min is None or carve[height-1, x] < min:
      minIndex = x
      min = carve[height-1, x]
  
  cx = minIndex
  path = [ [ height-1, cx]]
  
  for y in range( height-2, -1, -1 ):
    min = None
    minX = None
    for dx in [ cx-1, cx, cx+1 ]:
      if ( dx >= 0 ) and ( dx < width ):
        if min is None or carve[y,dx] < min:
          min = carve[y,dx]
          minX = dx
    cx = minX
    path.append([ y, cx ] )
  return path

minPath = np.array( findPath(carve) )
#print(minPath )

greedyPath = greedy_seam( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg )
ax.plot( minPath[:,1], minPath[:,0], 'b-', linewidth=3 )         
sol2 = addJBFigure( "sol2", 0, 0, fig )       
carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

print('Path', p, 'Energy', calc_energy(timg[:,1:10], p ) )
Path [[4, 5], [3, 4], [2, 4], [1, 5], [0, 6]] Energy 103
60.0 60.0 89.0 25.0 42.0 71.0 31.0 74.0 9.0
149.0 66.0 112.0 69.0 98.0 46.0 96.0 11.0 17.0
48.0 14.0 52.0 55.0 21.0 65.0 8.0 31.0 42.0
95.0 59.0 93.0 28.0 21.0 26.0 69.0 71.0 68.0
116.0 141.0 52.0 111.0 101.0 51.0 59.0 94.0 125.0
% matplotlib notebook 
def findPath( carve ):
  height, width = carve.shape
  minIndex = None
  min = None
  for x in range(width):
    if min is None or carve[height-1, x] < min:
      minIndex = x
      min = carve[height-1, x]
  
  cx = minIndex
  path = [ [ height-1, cx]]
  
  for y in range( height-2, -1, -1 ):
    min = None
    minX = None
    for dx in [ cx-1, cx, cx+1 ]:
      if ( dx >= 0 ) and ( dx < width ):
        if min is None or carve[y,dx] < min:
          min = carve[y,dx]
          minX = dx
    cx = minX
    path.append([ y, cx ] )
  return path

minPath = np.array( findPath(carve) )
#print(minPath )

greedyPath = greedy_seam( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg )
ax.plot( minPath[:,1], minPath[:,0], 'b-', linewidth=3 )
ax.plot( greedyPath[:,1], greedyPath[:,0], 'g-', linewidth=3 )

sol2 = addJBFigure( "sol2", 0, 0, fig )       

Seam Carving

% matplotlib notebook 
def findPath( carve ):
  height, width = carve.shape
  minIndex = None
  min = None
  for x in range(width):
    if min is None or carve[height-1, x] < min:
      minIndex = x
      min = carve[height-1, x]
  
  cx = minIndex
  path = [ [ height-1, cx]]
  
  for y in range( height-2, -1, -1 ):
    min = None
    minX = None
    for dx in [ cx-1, cx, cx+1 ]:
      if ( dx >= 0 ) and ( dx < width ):
        if min is None or carve[y,dx] < min:
          min = carve[y,dx]
          minX = dx
    cx = minX
    path.append([ y, cx ] )
  return path

minPath = np.array( findPath(carve) )
#print(minPath )

greedyPath = np.array( greedy_seam( grad ) )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg )
ax.plot( minPath[:,1], minPath[:,0], 'b-', linewidth=3 )
ax.plot( greedyPath[:,1], greedyPath[:,0], 'g-', linewidth=3 )

sol2 = addJBFigure( "sol2", 0, 0, fig )       

Seam Carving

% matplotlib notebook 
def findPath( carve ):
  height, width = carve.shape
  minIndex = None
  min = None
  for x in range(width):
    if min is None or carve[height-1, x] < min:
      minIndex = x
      min = carve[height-1, x]
  
  cx = minIndex
  path = [ [ height-1, cx]]
  
  for y in range( height-2, -1, -1 ):
    min = None
    minX = None
    for dx in [ cx-1, cx, cx+1 ]:
      if ( dx >= 0 ) and ( dx < width ):
        if min is None or carve[y,dx] < min:
          min = carve[y,dx]
          minX = dx
    cx = minX
    path.append([ y, cx ] )
  return path

minPath = np.array( findPath(carve) )
#print(minPath )

greedyPath = np.array( greedy_seam( grad ) )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg )
ax.plot( minPath[:,1], minPath[:,0], 'b-', linewidth=7 )
ax.plot( greedyPath[:,1], greedyPath[:,0], 'g-', linewidth=3 )

sol2 = addJBFigure( "sol2", 0, 0, fig )       

Seam Carving

% matplotlib notebook 
def findPath( carve ):
  height, width = carve.shape
  minIndex = None
  min = None
  for x in range(width):
    if min is None or carve[height-1, x] < min:
      minIndex = x
      min = carve[height-1, x]
  
  cx = minIndex
  path = [ [ height-1, cx]]
  
  for y in range( height-2, -1, -1 ):
    min = None
    minX = None
    for dx in [ cx-1, cx, cx+1 ]:
      if ( dx >= 0 ) and ( dx < width ):
        if min is None or carve[y,dx] < min:
          min = carve[y,dx]
          minX = dx
    cx = minX
    path.append([ y, cx ] )
  return path

carve = findMinEnergySeam( grad )
minPath = np.array( findPath(carve) )
#print(minPath )

greedyPath = np.array( greedy_seam( grad ) )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg )
ax.plot( minPath[:,1], minPath[:,0], 'b-', linewidth=7 )
ax.plot( greedyPath[:,1], greedyPath[:,0], 'g-', linewidth=3 )

sol2 = addJBFigure( "sol2", 0, 0, fig )       

Seam Carving

def removePath( img, path ):
  height, width, depth = img.shape
  new = np.zeros((height, width-1, depth))
  #print(img.shape, new.shape)

  for y,x in path:
    #r = img[y,:x+1] + img[y,x+1:]
    #print('x',x)
    new[y,0:x] = img[y,0:x]
    new[y,x:] = img[y,x+1:]
  return new
def carveSeam(origImg, NIter ):
  img = origImg.copy()
  for i in range(NIter):
    #print('Loop', i, 'Shape', img.shape)
    grad = calcGradient( img )
    carve = findMinEnergySeam( grad )
    minPath = np.array( findPath(carve) )
    #print('grad', grad.shape, 'carve', carve.shape, 'path', minPath[0:5] )
    img = removePath( img, minPath )

    # img = np.rot90( img )
    # grad = calcGradient( img )
    # carve = findMinEnergySeam( grad )
    # minPath = np.array( findPath(carve) )
    # #print('grad', grad.shape, 'carve', carve.shape, 'path', minPath[0:5] )
    # img = removePath( img, minPath )
    # img = np.rot90( img, 3 )
    
  return img.astype(np.uint8)

height, width, depth = oimg.shape
NIter = 100
simg = carveSeam( oimg, NIter )
print('simg', simg.shape)

fig = plt.figure( figsize=(12,10))
ax1 = fig.add_subplot(1,3,1)

ax1.imshow( oimg )

ax2 = fig.add_subplot(1,3,2)

ax2.imshow( simg )

ax3 = fig.add_subplot(1,3,3)
ax3.imshow( origImage.resize((width - NIter, height - NIter)))

sol10 = addJBFigure( "sol10", 0, 0, fig )
% matplotlib notebook 

import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
import math
import random

origImage = Image.open( img1.getLocalName() )
width, height = origImage.size

nw, nh = width//2, height//2
origImage = origImage.resize((nw,nh))
oimg = np.array( origImage )
#oimg = oimg[200:300,430:530]

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg, cmap='gray')

balir=addJBFigure("balir", 0, 0, fig )
%matplotlib notebook 

def calcGradientSlow( img ):
  height, width, depth = img.shape
  grad = np.zeros( ( height, width )  )
  #print(height, width, depth )
  for y in range( height ):
    for x in range( width ):
      gx, cnt = 0.0, 0
      for dx, dy in [ [-1,-1], [0,-1], [1,-1], [-1,0], [1,0], [1,-1], [1,0], [1,1] ]:
        x1 = x + dx
        y1 = y + dy
        if ( x1 >= 0 ) and ( x1 < width ) and ( y1 >= 0 ) and ( y1 < height ):
          d = np.sum( np.abs( img[y,x] - img[y1,x1] ) )
          
          gx = gx + d
          cnt = cnt + 1
      grad[y,x] = gx/cnt
  return grad

Seam Carving

https://i.postimg.cc/5NkcFtVS/sample-image.jpg https://i.postimg.cc/5NkcFtVS/sample-image.jpg

Detail is lost when resizing the image

Intelligent resize for images, focus on "interesting" parts

Energy

Interesting? Measure of information associated with a pixel

Measure how different from the background/its neighbors

One way to formalize energy is the magnitude of the gradient

% matplotlib notebook 

import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
import math
import random

origImage = Image.open( img1.getLocalName() )
width, height = origImage.size

nw, nh = width//2, height//2
origImage = origImage.resize((nw,nh))
oimg = np.array( origImage )
#oimg = oimg[200:300,430:530]

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg, cmap='gray')

balir=addJBFigure("balir", 0, 0, fig )
%matplotlib notebook 

def calcGradientSlow( img ):
  height, width, depth = img.shape
  grad = np.zeros( ( height, width )  )
  #print(height, width, depth )
  for y in range( height ):
    for x in range( width ):
      gx, cnt = 0.0, 0
      for dx, dy in [ [-1,-1], [0,-1], [1,-1], [-1,0], [1,0], [1,-1], [1,0], [1,1] ]:
        x1 = x + dx
        y1 = y + dy
        if ( x1 >= 0 ) and ( x1 < width ) and ( y1 >= 0 ) and ( y1 < height ):
          d = np.sum( np.abs( img[y,x] - img[y1,x1] ) )
          
          gx = gx + d
          cnt = cnt + 1
      grad[y,x] = gx/cnt
  return grad
%matplotlib notebook 

def normalizeImage( img ):
  return ( grad - np.min(grad) ) * 255.0 / np.max(grad)

#img = np.random.random( (10,10,3) ) *255
#img[0:10,5:8,:] = 128

grad = calcGradient( oimg )
gradNorm = normalizeImage( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( gradNorm, cmap = 'gray' )

bali10 = addJBFigure( "bali10", 0, 0, fig )
%matplotlib notebook 

def normalizeImage( img ):
  return ( grad - np.min(grad) ) * 255.0 / np.max(grad)

#img = np.random.random( (10,10,3) ) *255
#img[0:10,5:8,:] = 128

grad = calcGradient( oimg )
print('grad shape', grad.shape)
gradNorm = normalizeImage( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( gradNorm, cmap = 'gray' )

bali10 = addJBFigure( "bali10", 0, 0, fig )
grad shape (640, 147, 3)
%matplotlib notebook 

def normalizeImage( img ):
  return ( grad - np.min(grad) ) * 255.0 / np.max(grad)

#img = np.random.random( (10,10,3) ) *255
#img[0:10,5:8,:] = 128

grad = calcGradient( oimg )
print('grad shape', grad.shape)
gradNorm = normalizeImage( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( gradNorm, cmap = 'gray' )

bali10 = addJBFigure( "bali10", 0, 0, fig )
grad shape (640, 147)
%matplotlib notebook 

def normalizeImage( img ):
  return ( grad - np.min(grad) ) * 255.0 / np.max(grad)

#img = np.random.random( (10,10,3) ) *255
#img[0:10,5:8,:] = 128

grad = calcGradient( oimg )
print('grad shape', grad.shape)
gradNorm = normalizeImage( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( gradNorm, cmap = 'gray' )

bali10 = addJBFigure( "bali10", 0, 0, fig )
grad shape (640, 147)
%matplotlib notebook 

def normalizeImage( img ):
  return ( grad - np.min(grad) ) * 255.0 / np.max(grad)

#img = np.random.random( (10,10,3) ) *255
#img[0:10,5:8,:] = 128

oimg = origImage 

grad = calcGradient( oimg )
print('grad shape', grad.shape)
gradNorm = normalizeImage( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( gradNorm, cmap = 'gray' )

bali10 = addJBFigure( "bali10", 0, 0, fig )
grad shape (147, 640)

Remove Unwanted Artefacts

Overriding the energy heuristic for certain pixels

Force energy to be 0